import java.util.*;

public class SwordToOffer {

    // 剑指 Offer 03. 数组中重复的数字
    public int findRepeatNumber(int[] nums) {
        // 数组中的数字出现在一定范围内，用数组记录即可，然后出现记录次数多余1的即为重复数字
        int len = nums.length - 1, low = 0;
        int[] record = new int[len + 1];
        while (low < len) {
            record[nums[low]] += 1;
            record[nums[len]] += 1;
            if (record[nums[low]] > 1)
                return nums[low];
            if (record[nums[len]] > 1)
                return nums[len];
            low++;
            len--;
        }
        return 0;
    }

    // 剑指 Offer 04. 二维数组中的查找
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // m 行内递增，n 列内递增，顺序队列，二分是一个很好的查询方法
        // 右侧以及下侧的数据都较大，因此往左往上回缩
        // *** 要注意一些特殊情况,如 [[]] 0； [[-5]] -10； [] 1；等情况
        if (matrix.length == 0 || matrix[0].length == 0)
            return false;
        int mHigh = matrix.length, nHigh = matrix[0].length;
        while (matrix[mHigh - 1][0] > target) {
            --mHigh;
            if (mHigh == 0)
                return false;
        }
        while (matrix[0][nHigh - 1] > target) {
            --nHigh;
            if (nHigh == 0)
                return false;
        }
        for (int m = 0; m < mHigh; ++m) {
            for (int n = 0; n < nHigh; ++n) {
                if (matrix[m][n] == target)
                    return true;
            }
        }
        return false;
        // 线性寻找，把二维数组看成一维线性再去寻找
        // if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        // return false;
        // }
        // int rows = matrix.length, columns = matrix[0].length;
        // int row = 0, column = columns - 1;
        // while (row < rows && column >= 0) {
        // int num = matrix[row][column];
        // if (num == target) {
        // return true;
        // } else if (num > target) {
        // column--;
        // } else {
        // row++;
        // }
        // }
        // return false;
    }

    // 剑指 Offer 05. 替换空格
    public String replaceSpace(String s) {
        // StringBuffer，逐个字符判断，不为空直接添加，为空添加%20
        StringBuffer sBuffer = new StringBuffer();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == ' ') {
                sBuffer.append("%20");
            } else {
                sBuffer.append(s.charAt(i));
            }
        }
        return sBuffer.toString();
    }

    // 剑指 Offer 06. 从尾到头打印链表
    public int[] reversePrint(ListNode head) {
        // 数组解决：先顺序遍历得链表长，然后再顺序遍历链表反向插入结果数组实现O(n)时间复杂度，无需过多额外空间
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            ++len;
            temp = temp.next;
        }
        int[] ans = new int[len];
        while (head != null) {
            ans[len - 1] = head.val;
            --len;
            head = head.next;
        }
        return ans;
        // 递归初始化数组
        // int[] res;
        // int i = 0;
        // int j = 0;
        // public int[] reversePrint(ListNode head) {
        // solve(head);
        // return res;
        // }
        // public void solve(ListNode head){
        // if(head == null){
        // res = new int[i];
        // return;
        // }
        // i++;
        // solve(head.next);
        // res[j] = head.val;
        // j++;
        // }
    }

    // 剑指 Offer 07. 重建二叉树 ***
    class SolutionOfReBuildBinaryTree {
        private Map<Integer, Integer> indexMap;

        public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right,
                int inorder_left, int inorder_right) {
            if (preorder_left > preorder_right) {
                return null;
            }

            // 前序遍历中的第一个节点就是根节点
            int preorder_root = preorder_left;
            // 在中序遍历中定位根节点
            int inorder_root = indexMap.get(preorder[preorder_root]);

            // 先把根节点建立出来
            TreeNode root = new TreeNode(preorder[preorder_root]);
            // 得到左子树中的节点数目
            int size_left_subtree = inorder_root - inorder_left;
            // 递归地构造左子树，并连接到根节点
            // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree,
                    inorder_left, inorder_root - 1);
            // 递归地构造右子树，并连接到根节点
            // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right,
                    inorder_root + 1, inorder_right);
            return root;
        }

        public TreeNode buildTree(int[] preorder, int[] inorder) { // 递归方法
            int n = preorder.length;
            // 构造哈希映射，帮助我们快速定位根节点
            indexMap = new HashMap<Integer, Integer>();
            for (int i = 0; i < n; i++) {
                indexMap.put(inorder[i], i);
            }
            return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
        }

        public TreeNode buildTreeByIteration(int[] preorder, int[] inorder) { // 迭代方法
            if (preorder == null || preorder.length == 0) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[0]);
            Deque<TreeNode> stack = new LinkedList<TreeNode>();
            stack.push(root);
            int inorderIndex = 0;
            for (int i = 1; i < preorder.length; i++) {
                int preorderVal = preorder[i];
                TreeNode node = stack.peek();
                if (node.val != inorder[inorderIndex]) {
                    node.left = new TreeNode(preorderVal);
                    stack.push(node.left);
                } else {
                    while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                        node = stack.pop();
                        inorderIndex++;
                    }
                    node.right = new TreeNode(preorderVal);
                    stack.push(node.right);
                }
            }
            return root;
        }
    }

    // 剑指 Offer 09. 用两个栈实现队列
    class CQueue {
        // 两个栈，凡插入，进入s1栈；凡出，出s2栈，若s2为空，则全部s1元素出栈并进栈s2
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();

        public CQueue() {
            s1.clear();
            s2.clear();
        }

        public void appendTail(int value) {
            s1.push(value);
        }

        public int deleteHead() {
            if (s2.isEmpty()) {
                if (s1.isEmpty())
                    return -1;
                else {
                    while (!s1.isEmpty())
                        s2.push(s1.pop());
                }
            }
            return s2.pop();
        }
    }

    // 剑指 Offer 10- I. 斐波那契数列
    class SolutionOfFib {
        public int fib(int n) {
            int a = 0, b = 1, sum = 0;
            for (int i = 0; i < n; ++i) {
                sum = (a + b) % 1000000007;
                a = b;
                b = sum;
            }
            return a;
        }

        public int fibByDp(int n) { // 动态规划
            // if (n == 0)
            // return 0;
            // int[] dp = new int[n + 1];
            // dp[0] = 0;
            // dp[1] = 1;
            // for (int i = 2; i <= n; i++) {
            // dp[i] = dp[i - 1] + dp[i - 2];
            // dp[i] %= 1000000007;
            // }
            // return dp[n];
            if (n == 0)
                return 0;
            int left = 0, mid = 1, right = 1;
            for (int i = 2; i <= n; i++) {
                right = (left + mid) % 1000000007;
                left = mid;
                mid = right;
            }
            return right;
        }
    }

    // 剑指 Offer 11. 旋转数组的最小数字
    class SolutionOfminArray {
        public int minArray(int[] numbers) {
            int res = Integer.MAX_VALUE;
            for (int i : numbers) {
                res = Math.min(res, i);
            }
            return res;
        }

        public int minArrayOfBinary(int[] numbers) {
            int low = 0;
            int high = numbers.length - 1;
            while (low < high) {
                int pivot = low + (high - low) / 2;
                // 这里的判断情况一定要找对
                // 最小值可能出现在任意位置，且最小值得左边以及右边不是空就一定是有序数列，即 递增 | 最小值 | 递增
                // 因此可以采用而二分法，***找的是最小值，因此出现中间值较小的情况，则一定high或者low = mid，若出现大于的情况，则一定等于mid +- 1
                if (numbers[pivot] < numbers[high]) { // 中间值小于右侧的，则最小值一定出现左边这一部分
                    high = pivot;
                } else if (numbers[pivot] > numbers[high]) {// 中间值若大于右侧的，则最小值一定出现在右边这一部分
                    low = pivot + 1;
                } else { // 否则high--
                    high -= 1;
                }
            }
            return numbers[low];
        }
    }

    // 剑指 Offer 12. 矩阵中的路径
    class SolutionOfMatirxExist {
        public boolean exist(char[][] board, String word) {
            char[] words = word.toCharArray();
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (dfs(board, words, i, j, 0))
                        return true;
                }
            }
            return false;
        }

        boolean dfs(char[][] board, char[] word, int i, int j, int k) {
            if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k])
                return false;
            if (k == word.length - 1)
                return true;
            board[i][j] = '\0';
            boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1)
                    || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
            board[i][j] = word[k];
            return res;
        }
    }

    // 剑指 Offer 13. 机器人的运动范围
    class SolutionOfRobotMove {
        int m, n, k;
        boolean[][] visited;

        public int movingCountOfDFS(int m, int n, int k) {
            this.m = m;
            this.n = n;
            this.k = k;
            this.visited = new boolean[m][n];
            return dfs(0, 0, 0, 0);
        }

        public int dfs(int i, int j, int si, int sj) {
            if (i >= m || j >= n || k < si + sj || visited[i][j])
                return 0;
            visited[i][j] = true;
            return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj)
                    + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
        }

        public int movingCountOfBFS(int m, int n, int k) {
            if (k == 0) {
                return 1;
            }
            Queue<int[]> queue = new LinkedList<int[]>();
            // 向右和向下的方向数组
            int[] dx = { 0, 1 };
            int[] dy = { 1, 0 };
            boolean[][] vis = new boolean[m][n];
            queue.offer(new int[] { 0, 0 });
            vis[0][0] = true;
            int ans = 1;
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                for (int i = 0; i < 2; ++i) {
                    int tx = dx[i] + x;
                    int ty = dy[i] + y;
                    if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
                        continue;
                    }
                    queue.offer(new int[] { tx, ty });
                    vis[tx][ty] = true;
                    ans++;
                }
            }
            return ans;
        }

        private int get(int x) {
            int res = 0;
            while (x != 0) {
                res += x % 10;
                x /= 10;
            }
            return res;
        }
    }

    // 剑指 Offer 14- I. 剪绳子

    // 剑指 Offer 14- II. 剪绳子 II

    // 剑指 Offer 15. 二进制中1的个数
    public class SolutionOfhammingWeight {
        // you need to treat n as an unsigned value

        public int hammingWeight(int n) {
            int res = 0;
            while (n != 0) {
                res += n & 1; // 判断结尾是否为1
                n >>>= 1; // 移位
            }
            return res;
        }

        public int hammingWeight2(int n) {
            int res = 0;
            while (n != 0) {
                ++res;
                n &= n - 1; // 精髓所在
            }
            return res;
        }
    }

    // 剑指 Offer 17. 打印从1到最大的n位数
    class SolutionOfprintNumbers {
        public int[] printNumbers(int n) {
            int len = (int) Math.pow(10, n);
            int[] res = new int[len];
            for (int i = 1; i < len; ++i) {
                res[i - 1] = i;
            }
            return res;
        }
    }

    // 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
    class SolutionOfexchange {
        // 双指针插入
        public int[] exchange(int[] nums) {
            int len = nums.length;
            int[] res = new int[len];
            int top = 0, bot = len - 1;
            for (int i = 0; i < len; ++i) {
                if (nums[i] % 2 == 0)
                    res[bot--] = nums[i];
                else
                    res[top++] = nums[i];
            }
            return res;
        }

        // 首尾快慢双指针
        public int[] exchange2(int[] nums) {
            int len = nums.length;
            int top = 0, bot = len - 1;
            while (bot >= top) {
                // 要注意这里的指针溢出情况
                while (nums[top] % 2 != 0 && top < len - 1)
                    top++;
                while (nums[bot] % 2 == 0 && bot > 0)
                    bot--;
                if (bot <= top)
                    return nums;
                int temp = nums[top];
                nums[top] = nums[bot];
                nums[bot] = temp;
            }
            return nums;
        }
    }
}
